(1) Field of the Invention
The present invention relates to an image data encoding system, and more particularly to a method and an apparatus for pattern matching encoding in which the number of codes can be reduced.
(2) Description of the Related Art
An example of the technique of the kind to which the present invention relates is disclosed under the title xe2x80x9cLossless and Lossy Compression of Test Images by Soft Pattern Matchingxe2x80x9d by Paul G. Howard (AT and T Bell Labs.) in ISO/IEC JTC 1/SC 29/WGI N205, issued on Jun. 30, 1995, pp. 1-29).
The above technique is an effective encoding method mainly for binary image data including letter images, and adopts pattern matching for the encoding. In this method, patterns are extracted in small units, such as a letter or letters, from an image (the extracted images being hereinafter referred to as xe2x80x9cpatternsxe2x80x9d). The pattern extraction is made by a well-known method such as a boundary tracing method.
The extracted patterns are compared with letter image data (hereinafter referred to as xe2x80x9clibraryxe2x80x9d) having been preliminarily prepared and stored. When the same letter image as the pattern exists in the library, the library image is simultaneously referred to during the encoding of the pattern. The reference to the pattern and library is made at a region of pixels (a dozen or so) called a template. The region is shifted for the entire pattern (and library) to carry out sequential encoding.
The template adopts a form which has proven to be highly efficient through experiments. Even such a highly efficient template form, however, may not be optimum depending on the characteristics of the letter image, and in such a case the encoding efficiency is deteriorated.
Thus, in the prior art, when the encoding is carried out utilizing the pattern matching, the form that the template adopts cannot be optimum depending on the pattern characteristics thus resulting in unsatisfactory encoding efficiency.
An object of the present invention, therefore, is to overcome the problems existing in the prior art, and to provide a method and an apparatus for pattern matching encoding in which the number of codes can be reduced, thus improving the efficiency of code transmission and also the efficiency of code accumulation.
According to an aspect of the invention, there is provided a method for pattern matching encoding of patterns in input binary or multi-level image data, the method comprising the steps of:
segment-checking as to which line segments in directions in an image a pixel being processed is positioned on; and
encoding by switching templates with optimum forms based on a result of the segment-checking such that efficiency of the encoding is enhanced.
More specifically, the method for pattern matching of the invention comprises:
a first step of extracting patterns from the image data supplied from an input terminal;
a second step of accumulating each extracted pattern and executing a match check thereof with patterns that have been accumulated;
a third step of checking, when a match pattern is found, for each pixel in the match pattern as to which line segments in directions the pixel is positioned on;
a fourth step of selecting an optimum template according to the line segment determined as a result of the segment checking; and
a fifth step of encoding the extracted pattern by an arithmetic encoding method with the selected template.
The step for checking the line segments may be made with respect to at least a horizontal line segment, a vertical line segment and a slanted line segment.
According to another aspect of the invention, there is also provided an apparatus for pattern matching encoding of patterns, comprising:
a pattern extracting unit for extracting patterns from input binary or multi-level image data;
an accumulating/match-checking unit for accumulating each extracted pattern and executing a match check thereof with patterns that have been accumulated;
a line segment checking unit for checking each pixel in the match pattern or the extracted pattern as to which line segment in directions the pixel is positioned on; and
an encoding unit for encoding the extracted pattern by selecting a template having an optimum form according to the result of the line segment checking.
In the above apparatus, the line segment check in the line segment checking unit may be made at least with respect to a horizontal line segment, a vertical line segment and a slanted line segment.
In the above apparatus, the encoding unit includes a first signal switching unit for sorting out match patterns, a second signal switching unit for sorting out extracted patterns, a plurality of template units corresponding to the horizontal, vertical and slanted line segments, and an arithmetic encoding unit. The first signal switching unit supplies the match pattern to either one of the template units according to the result of the line segment checking. The second signal switching unit supplies the extracted pattern to either one of the template units according to the result of the line segment checking. The template units output a template value by referring simultaneously to the match and extracted patterns. The arithmetic encoding unit arithmetically encodes the template value received from the template units and outputting code data.